#include "bits/stdc++.h"
using namespace std;


/**
 * @brief 给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
 * 
 */
class Solution {
    int dir_x[4] = {0, 1, 0, -1};
    int dir_y[4] = {1, 0, -1, 0};
    vector<vector<bool>> used;
public:
    bool exist(vector<vector<char>>& board, string word) {
        int m = board.size();
        int n = board[0].size();

        used = vector(m, vector<bool>(n, false));
        for (int i = 0; i < board.size(); ++i) {
            for (int j = 0; j < board[i].size(); ++j) {
                if (board[i][j] == word[0]) {
                    used[i][j] = true;
                    if (dfs(i, j, board, word, 1))
                        return true;
                    used[i][j] = false;
                }
            }
        }
        return false;
    }

    bool dfs(int i, int j, vector<vector<char>>& board, string &word, int id) {
        if (id == word.size()) {
            return true;
        }

        for (int k = 0; k < 4; k++) {
            int x = i + dir_x[k];
            int y = j + dir_y[k];

            if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size() && used[x][y] == false && word[id] == board[x][y]) {
                used[x][y] = true;
                if (dfs(x, y, board, word, id + 1))
                    return true;
                used[x][y] = false; 
            }
        }

        return false;
    }
};